#include "structs.h"
#include "Root.h"
/*************************************************
  узел дерева состоит из 2n полей для хранения
  данных и из двух служебных:
  1) первый элемент узла(list[0]) используется для ссылания
  на поддерево с узлами, имеющими ключи менее минимального
  в данном узле.
  2) (2n+2)-й узел(list[2n+1]) используется как буфферный элемент
  в том случае, когда при добавлении нового элемента происходит
  разделение узла на два. (split_insert()).
  ************************************************/
Node::Node (Root& root_track) :
    count(0),
    parent(0),
    root(root_track),
    mQNode(0)
{
    list.resize (DEFAULT_NODE_COUNT+2);
    //count = 0;
    //parent = 0;
    insert_zeroth_subtree (0);

    connect(this, SIGNAL(nodeCreated(Node*)), &root, SLOT(nodeCreatedHandler(Node*)));
    connect(this, SIGNAL(nodeChanged(Node*)), &root, SLOT(nodeChangedHandler(Node*)));
    connect(this, SIGNAL(fatherChanged(Node*)), &root, SLOT(fatherChangedHandler(Node*)));
    connect(this, SIGNAL(nodeDestroyed(Node*)), &root, SLOT(nodeDestroyedHandler(Node*)));

    emit nodeCreated(this);
}
 /***********************************************
  *                                             *
  *                 INSERT BLOCK                *
  *                                             *
  ***********************************************/
bool Node::tree_insert (Elem& element)
{
    Node* last_visited_ptr = this;
    // если элемент уже существует в дереве, тогда
    // добавления не производим
    if (search(element, last_visited_ptr).valid())
        return false;
    // попытка вставить в текущий узел
    if (last_visited_ptr->vector_insert(element,false))
        return true;
    // добавление с разделением узла
    return last_visited_ptr->split_insert(element);
}
//________________________________________________________________________

bool Node::vector_insert (Elem& element,bool isSplitInsert) {
    /**** в данном методе прозводим вставку непосредственно в узел****/

    // проверяем наличие свободного места в узле
    if (((unsigned)count >= list.size()-1 && !isSplitInsert)
     || ((unsigned)count >= list.size() && isSplitInsert))
        return false;
    int i = count;
    // сдвиг вправо, если необходимо
    while (i>0 && list[i-1]>element) {
        list[i] = list[i-1];
        i--;
    }
    // в нелистовом узле нужно сменить указатель на отца у потомка
    if (element.subtree())
        element.subtree()->setFather(this);

    list[i] = element;
    count++;

    if (!isSplitInsert)
        emit nodeChanged(this); // signal
    return true;
}
//________________________________________________________________________

bool Node::split_insert (Elem& element) {
    /**** метод вызывается, когда узел переполнен****/
    if (count != (signed)(list.size()-1))
        throw "bad count in split_insert";

    vector_insert(element, true);
    // находим средний элемент, который вытолкнем
    int split_point = count/2;
    if (2*split_point < count)
        split_point++;
    // создаем новый узел и копируем туда правую половину элементов
    // upward_element - выталкиваемый вверх элемент.
    Node* new_node = new Node(root);
    Elem upward_element = list[split_point];
    new_node->insert_zeroth_subtree (upward_element.subtree());
    upward_element.setSubtree(new_node);

    // собственно копирование правой части узла в новый узел
    for (int i=1; i<count-split_point; i++)
        new_node->vector_insert(list[split_point+i],false);

    new_node->count = count-split_point;
    count = split_point;
    new_node->setFather(parent);

    // теперь непосредственно выталкивание среднего элемента узла вверх
    if (parent && parent->vector_insert(upward_element,false)){
        /****************SIGNAL ZONE**********************/
        emit nodeChanged(this);     // signal
        emit fatherChanged(this);//signal
        emit nodeChanged(new_node); // signal
        emit fatherChanged(new_node); //signal
        if (new_node->list[0].subtree())
            emit fatherChanged(new_node->list[0].subtree()); // signal

        for (int i=0;i< parent->count; ++i)
            if (parent->list[i].subtree())
                emit fatherChanged(parent->list[i].subtree());
        /**************************************************/

        return true;
    }
    else if (parent && parent->split_insert(upward_element)){
        /****************SIGNAL ZONE**********************/
        emit nodeChanged(this);     // signal
        emit fatherChanged(this);//signal
        emit nodeChanged(new_node); // signal
        emit fatherChanged(new_node); //signal
        if (new_node->list[0].subtree())
            emit fatherChanged(new_node->list[0].subtree()); //signal
        for (int i=0;i< parent->count; ++i)
            if (parent->list[i].subtree())
                emit fatherChanged(parent->list[i].subtree());
        /**************************************************/
        return true;
    }
    else if (!parent) {
        Node* new_root = new Node(root); // Root ? o_O
        new_root->insert_zeroth_subtree(this);
        this->setFather(new_root);
        new_node->setFather(new_root);
        new_root->vector_insert (upward_element,false);
        root.set_root (root.get_root(),  new_root);
        new_root->setFather(0);
       /* for (int i=0;i < root.get_root()->count; ++i)
            if (root.get_root()->list[i].subtree())
                emit fatherChanged(root.get_root()->list[i].subtree());
        */
   }
    /****************SIGNAL ZONE**********************/
    emit nodeChanged(this);     // signal
    emit fatherChanged(this);//signal
    emit nodeChanged(new_node); // signal
    emit fatherChanged(new_node); //signal
    if (new_node->list[0].subtree())
        emit fatherChanged(new_node->list[0].subtree()); // signal
    for (int i=0;i< parent->count; ++i)
        if (parent->list[i].subtree())
            emit fatherChanged(parent->list[i].subtree());
    /**************************************************/
   // for (int i=0;i < root.get_root()->count; ++i)
    //    if (root.get_root()->list[i].subtree())
    //        emit fatherChanged(root.get_root()->list[i].subtree());
    return true;
}
//________________________________________________________________________

void Node::insert_zeroth_subtree (Node* subtree)
{
    list[0].setSubtree(subtree);
    list[0].setKey(0);
    count = 1;
    if (subtree)
        subtree->setFather(this);
    emit nodeChanged(this);     // signal
    emit nodeChanged(subtree);     // signal

}
/***********************************************
 *                                             *
 *                 DELETE BLOCK                *
 *                                             *
 ***********************************************/
bool Node::delete_element (Elem& target) {
    Node* node = 0;
    int parent_index_this = INVALID_INDEX;
    // поиск элемента по ключу, и его валидация
    Elem& found = search (target, node);
    if (!found.valid())
        return false;
    // самый простой вариант удаления, когда элемент в листовом узле
    // и количество элементов в узле больше чем n
    if (node->is_leaf() && node->key_count() > node->min_keys())
        return node->vector_delete (target);
    // удаляемый элемент в листе, но в нем содержится всего n элементов
    else if (node->is_leaf())
    {
        node->vector_delete (target);
        // удалили элемент с узла, в нем находится теперь менее n элементов.
        // тепер нужно произвести переливание или слияние.
        while (node)
        {
            // валидация для node (после первой итерации данного цикла может нарушиться)
            if (node==node->find_root() && node->is_leaf())
                break;
            if (node==node->find_root() && !node->is_leaf())
                throw "node should not be root in delete_element loop";

            // попытка взаимствовать "лишний" элемент у правого брата
            Node* right = node->right_sibling(parent_index_this);
            if (right && right->key_count() > right->min_keys())
            {
                node = node->rotate_from_right(parent_index_this);
                //emit nodeChanged(this); //signal
                //emit nodeChanged(right); //signal
            }

            else
            {
                // попытка взаимствовать "лишний" элемент у левого брата
                Node* left = node->left_sibling(parent_index_this);
                if (left && left->key_count() > left->min_keys())
                {
                    node = node->rotate_from_left(parent_index_this);
                    //emit nodeChanged(left); //signal
                }
                // если не получилось перелить, тогда пытаемся слить два узла
                else if (right)
                    node = node->merge_right(parent_index_this);
                else if (left)
                    node = node->merge_left(parent_index_this);
               //! emit nodeChanged(this); //signal
            }
        } // while
    }  // else if
    else
    {
        Elem& smallest_in_subtree = found.subtree()->smallest_key_in_subtree();
        found.setKey(smallest_in_subtree.key());
        found.setData(smallest_in_subtree.data());
        found.subtree()->delete_element (smallest_in_subtree);
        //! emit nodeChanged(this); //signal
    }
    return true;
}
//___________________________________________________________________

bool Node::vector_delete (Elem& target)
{
    for (int target_pos = 1; target_pos < count ; target_pos++){
        if (list[target_pos] == target){
            // просто затираем удаляемый элемент
            for (int i=target_pos; i<count; i++)
                list[i] = list[i+1];
            // уменьшаем счетчик к-ва элементов в узле
            count--;
            emit nodeChanged(this); //signal
            return true;
        }
    }
    return false;
}

//____________________________________________________________________

bool Node::vector_delete (int target_pos) {
    if (target_pos < 0 || target_pos >= count) return false;
    // затираем удаляемый элемент
    for (int i=target_pos; i<count; i++)
        list[i] = list[i+1];
    // уменьшаем счетчик к-ва элементов в узле
    count--;
    emit nodeChanged(this); //signal
    return true;
}

//____________________________________________________________________


int Node::delete_all_subtrees () {
// удаляем все поддерево у узла и возвращаем к-во удаленных узлов
    int count_deleted = 0;
    for (int i=0; i< count; i++) {
        if (!list[i].subtree())
            continue;
        else if (list[i].subtree()->is_leaf()) {
            emit nodeDestroyed(list[i].subtree());
            delete list[i].subtree();            
            count_deleted++;            
            emit nodeChanged(this); //signal
        }
        else
            count_deleted += list[i].subtree()->delete_all_subtrees();
    }
    return count_deleted;
}

//_______________________________________________________________________


Node* Node::rotate_from_right(int parent_index_this) {
    // элемент с родительского узла который опустим в текущий узел
    Elem underflow_filler = parent->list[parent_index_this+1];
    // правый брат текущего узла
    Node* right_brother = parent->list[parent_index_this+1].subtree();
    underflow_filler.setSubtree(right_brother->list[0].subtree());
    // перемещаем в parent самы меньший элемент правого узла
    parent->list[parent_index_this+1] = right_brother->list[1];
    // корректируем указатели
    parent->list[parent_index_this+1].setSubtree(right_brother);
    vector_insert (underflow_filler,false);
    right_brother->vector_delete(0);
    right_brother->list[0].setKey(0);
    right_brother->list[0].setData("");

    emit nodeChanged(this); //signal
    emit nodeChanged(right_brother); //signal
    emit nodeChanged(parent); //signal
    if(underflow_filler.subtree())
        emit fatherChanged(underflow_filler.subtree()); //signal
    if (parent->list[parent_index_this+1].subtree())
        emit fatherChanged(parent->list[parent_index_this+1].subtree());
    return NULL;
}
//_______________________________________________________________________


Node* Node::rotate_from_left(int parent_index_this) {
    // элемент с родительского узла который опустим в текущий узел
    Elem underflow_filler = parent->list[parent_index_this];
    // левый брат текущего узла
    Node* left_brother = parent->list[parent_index_this-1].subtree();
    underflow_filler.setSubtree(this->list[0].subtree());
    this->list[0].setSubtree(left_brother->list[left_brother->count-1].subtree());

    if (this->list[0].subtree())
        this->list[0].subtree()->setFather(this);
    // перемещаем найбольший элемент с левого узла в parent
    parent->list[parent_index_this] = left_brother->list[left_brother->count-1];
    // корректируем указатели
    parent->list[parent_index_this].setSubtree(this);
    vector_insert (underflow_filler,false);
    left_brother->vector_delete(left_brother->count-1);

    emit nodeChanged(this); //signal
    emit nodeChanged(left_brother); //signal
    emit nodeChanged(parent); //signal
    if (underflow_filler.subtree())
        emit fatherChanged(underflow_filler.subtree()); //signal
    if (this->list[0].subtree())
        emit fatherChanged(this->list[0].subtree()); //signal
    if (parent->list[parent_index_this].subtree())
        emit fatherChanged(parent->list[parent_index_this].subtree());
    return NULL;
}

//_______________________________________________________________________

Node* Node::merge_right (int parent_index_this) {
/** в данном методе проводится слияние оставшихся элементов
    текущего узла (this) с правым узлом (right_brother) **/

    Elem parent_elem = parent->list[parent_index_this+1];
    Node* right_brother = parent->list[parent_index_this+1].subtree();
    parent_elem.setSubtree(right_brother->list[0].subtree());
    // в текущий узел опускаем элемент с родительского узла
    vector_insert (parent_elem,false);
    // копируем оставшиеся элементы с правого узла в текущий
    for (int i=1; i<right_brother->count; i++)
        vector_insert (right_brother->list[i],false);

    emit fatherChanged(parent_elem.subtree());

    parent->vector_delete (parent_index_this+1);
    // удаляем правый узел

    emit nodeChanged(parent);
    emit nodeDestroyed(right_brother);

    delete right_brother;
    // если в данный узел - корень и он остался пуст,
    // то он удаляется и корнем становится текущий узел
    if (parent==find_root() && !parent->key_count()) {
        root.set_root(root.get_root(), this);
        emit nodeDestroyed(parent);
        delete parent;
        setFather(0);
        emit nodeChanged(this);
        emit fatherChanged(this);
        return NULL;
    }
    // родительский узел - корень, но у него достаточно элементов
    else if (parent==find_root() && parent->key_count())
        return NULL;
     // если в родительском узле остается n элементов (достаточно)
    if (parent && parent->key_count() >= parent->min_keys())
        return NULL;
    // если в родительском узле недостаточно элементов (< n)
    return parent;

}
//_______________________________________________________________________

Node* Node::merge_left (int parent_index_this) {
/** в данном методе проводится слияние оставшихся элементов
    текущего узла (this) с левым узлом (left_brother) **/

    Elem parent_elem = parent->list[parent_index_this];
    parent_elem.setSubtree(this->list[0].subtree());
    Node* left_brother = parent->list[parent_index_this-1].subtree();
    // элемент с родительского узла опускаем влево
    left_brother->vector_insert (parent_elem,false);
    // перемещаем элементы с текущего узда влево
    for (int i=1; i<count; i++)
        left_brother->vector_insert (list[i],false);

    emit fatherChanged(parent_elem.subtree());

    parent->vector_delete (parent_index_this);
    Node* parent_node = parent;
    // если в данный узел - корень и он остался пуст,
    // то он удаляется и корнем становится левый брат
    if (parent==find_root() && !parent->key_count()) {
        root.set_root(root.get_root(), left_brother);
        emit nodeDestroyed(parent);
        delete parent;
        left_brother->setFather(NULL);

        emit nodeChanged(left_brother);
        emit nodeDestroyed(this);
        emit fatherChanged(left_brother);

        delete this;        
        return NULL;
    }
    // родительский узел - корень, но у него достаточно элементов
    else if (parent==find_root() && parent->key_count()) {
        emit nodeDestroyed(this);
        delete this;
        return NULL;
    }
    // удаляем текущий узел
    emit nodeDestroyed(this);
    delete this;
    // если в родительском узле остается n элементов (достаточно)
    if (parent_node->key_count() >= parent_node->min_keys())
        return NULL;
    // если в родительском узле недостаточно элементов (< n)
    return parent_node;
}
//_______________________________________________________________________
Node* Node::right_sibling (int& parent_index_this) {
    // находим индекс элемента в родительском узле,
    // сыном которого является текущий узел
    parent_index_this = getParentIndex ();
    if (parent_index_this == INVALID_INDEX)
        return 0;
    if (parent_index_this >= parent->count-1)
        return 0;  // справа нечего позаимствовать
    return parent->list[parent_index_this+1].subtree();  // might be null
}
//__________________________________________________________________________
Node* Node::left_sibling (int& parent_index_this) {
    // находим индекс элемента в родительском узле,
    // сыном которого является текущий узел
    parent_index_this = getParentIndex ();
    if (parent_index_this == INVALID_INDEX)
        return 0;
    if (parent_index_this==0)
        return 0;  // в левом узле нет свободного элемента
    return parent->list[parent_index_this-1].subtree();  // might be null
}
/***********************************************
 *                                             *
 *          SEARCH AND UTILITY BLOCK           *
 *                                             *
 ***********************************************/
Elem& Node::search (Elem& desired, Node*& last_visited_ptr) {
    /****
    Метод осуществляет поиск элемента в дереве по ключу.
    Поиск в данном методе происходит начиная с улза,
    на котором был вызван метод (не обязательно с корня).
    desired - ссылка на элемент который нужно найти.
    last_visited_ptr - ссылка на указатель на последний иссдедованый узел.
    ****/
    Node* current = this;
    if (!key_count()) // пустой узел - fail.
        current = 0;
    while (current)
    {
        last_visited_ptr = current;
        // если текущий элемент (current) меньше самого меньшего в узле,
        // то опускаемся вниз по самому левому указателю на поддерево.
        if ((current->count > 1) && (desired < current->list[1]))
            current = current->list[0].subtree();
        // если текущий элемент больше самого большего в узле,
        // то опускаемся вниз по самому  правому указателю на поддерево.
        else if (desired > current->list[current->count-1])
            current = current->list[current->count-1].subtree();
        // если элемент не меньше самого меньшего и не больше самого большого в узле,
        // то он находится либо в этом узле, либо в поддереве, ссылка на которое
        // находится в элементе межу самым маленьким и самым большим элементом текущего узла.
        else
        {
            for (int i = 1; i < current->count; i++)
            {
                if (current->list[i] == desired)
                    return current->list[i];
                if (current->list[i] > desired){
                    current = current->list[i-1].subtree();
                    break;
                }
            }
            if (last_visited_ptr == current)
                current = current->list[current->count-1].subtree();
        }
    }
    return fail;
}
/**** Поиск корня начиная с текущего узла. ****/
Node* Node::find_root () {
    Node* current = this;
    while (current->parent)
        current = current->parent;
    return current;
}

/**** Поиск индекса элемента в родительском узле,
      сыном которого является текущий узел. ****/
int Node::getParentIndex () {
    if (!parent) return INVALID_INDEX;
    for (int parent_index = 0; parent_index < parent->count; parent_index++){
        if (parent->list[parent_index].subtree() == this )
            return parent_index;
    }
    throw "error in getParentIndex";
}

/**** Поиск найменьшего узла в поддереве. ****/
Elem& Node::smallest_key_in_subtree () {
    if (is_leaf()) return list[1];
    else return list[0].subtree()->smallest_key_in_subtree();
}

// Минимально допустимое количество элементов в узле.
int Node::min_keys () { return (list.size() - 2) / 2; }
// Является ли текущий узел листом?
bool Node::is_leaf () { return list[0].subtree() == 0;}

// Используется с целью отладки - вывод дерева на консоль.
void Node::dump (){
        if (this == root.get_root())
            qDebug() << "ROOT\n";

        qDebug() << "this" << this;
        qDebug() << "       parent = " << parent << " count = " << count - 1 << endl;
        for (int i=1; i<count; i++)
            list[i].dump();
        //qDebug() << endl;
        for (int i=0; i<count; i++)
            if (list[i].subtree())
                list[i].subtree()->dump();
        qDebug() << endl;
}

//---------------------------------------------------------
Node* Node::getFather() const { return parent; }
void Node::setFather(Node *father)
{
    if ( father != parent )
    {
        parent = father;
        //emit fatherChanged(this);
    }
}

//---------------------------------------------------------
int Node::getCount() const { return count; }

// Инициализация статический данных
Elem Node::fail = Elem();
